Kadane's Algorithm

contents

카데인 알고리즘은 최대 부분 배열 합(Maximum Subarray Problem) 문제를 해결하는 가장 효율적이고 표준적인 방법입니다.

문제 정의:

정수 배열(음수 포함 가능)이 주어졌을 때, 합이 가장 큰 연속된 부분 배열(Contiguous Subarray) 을 찾으시오. (단, 최소 1개의 숫자는 포함해야 함)

• 입력: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
• 출력: 6
• 설명: 부분 배열 [4, -1, 2, 1]의 합이 6으로 가장 큽니다.

브루트 포스(완전 탐색) 방식은 $O(N^2)$이나 $O(N^3)$이 걸리지만, 카데인 알고리즘은 $O(N)$ (선형 시간) 과 $O(1)$ (상수 공간) 만으로 해결합니다.

1. 핵심 직관: "새로 시작할까?"

이 알고리즘은 배열을 딱 한 번 순회하며 매 단계마다 단순한 질문을 던집니다.

"앞에서부터 가져온 합이 나에게 도움이 되는가, 아니면 짐만 되는가?"

배열을 걸어가며 합을 누적하고 있다고 상상해 보세요.

1. 현재 인덱스 $i$에 도착했습니다.
2. $i-1$까지 계산된 current_sum을 가지고 있습니다.
3. 결정:
   • current_sum이 양수라면? 더하면 값이 커지니 챙겨갑니다 (nums[i]를 더함).
   • current_sum이 음수라면? 더해봤자 내 값만 깎아먹습니다. 과감히 버리고 nums[i]부터 새로 시작합니다.

2. 수학적 원리 (동적 계획법)

$local_max[i]$를 인덱스 $i$에서 끝나는 부분 배열의 최대 합이라고 정의합시다.

점화식(Recurrence Relation)은 다음과 같습니다.

$$local_max[i] = \max(A[i], \quad A[i] + local_max[i-1])$$

• $A[i]$: 이전 합을 버리고 여기서부터 새로운 구간을 시작한다.
• $A[i] + local_max[i-1]$: 이전 구간을 현재까지 확장한다.

최종 정답은 구해진 모든 $local_max$ 값들 중 최댓값입니다.

3. 트레이스 테이블 (단계별 시각화)

유명한 예제로 알고리즘을 추적해 보겠습니다.

A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

두 가지 변수를 유지합니다.

1. Current: 현재 위치에서 끝나는 최대 합.
2. Global: 지금까지 발견된 전체 최대 합.

초기화:

• Current = $A[0] = -2$
• Global = $A[0] = -2$

결과: 전체 최대 합(Global Max)은 6입니다.

4. 구현 코드 (Java)

중요한 엣지 케이스:

만약 배열이 모두 음수라면(예: [-5, -2, -9]), 답은 그중 가장 큰 값(-2)이어야 합니다.

• 잘못된 방법: maxSoFar = 0으로 초기화 (이러면 빈 배열을 의미하는 0이 반환됨).
• 올바른 방법: maxSoFar = nums[0] (첫 번째 원소)로 초기화.

public class KadaneAlgo {
    public int maxSubArray(int[] nums) {
        // 예외 처리
        if (nums == null || nums.length == 0) return 0;

        // 첫 번째 원소로 초기화
        int currentMax = nums[0];
        int globalMax = nums[0];

        // 두 번째 원소부터 루프 시작
        for (int i = 1; i < nums.length; i++) {
            // 선택: 여기서 새로 시작할지 OR 이전 합에 얹어갈지
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            
            // 신기록을 달성했는지 확인
            if (currentMax > globalMax) {
                globalMax = currentMax;
            }
        }
        
        return globalMax;
    }
}

5. 심화: 시작과 끝 인덱스 찾기

단순히 합(6)만 구하는 게 아니라, 그 합을 만드는 구간 [4, -1, 2, 1]을 알아야 할 때가 있습니다.

알고리즘을 조금 수정하면 인덱스도 추적할 수 있습니다.

public void printMaxSubArrayIndices(int[] nums) {
    int maxSoFar = Integer.MIN_VALUE;
    int currentMax = 0;
    int start = 0, end = 0, tempStart = 0;

    for (int i = 0; i < nums.length; i++) {
        currentMax += nums[i];

        if (currentMax > maxSoFar) {
            maxSoFar = currentMax;
            start = tempStart; // 실제 시작점 갱신
            end = i;           // 실제 끝점 갱신
        }

        // 합이 0보다 작아지면, 그 구간은 버리는 게 낫습니다.
        if (currentMax < 0) {
            currentMax = 0;
            tempStart = i + 1; // 잠재적인 새로운 시작점은 다음 인덱스
        }
    }
    
    System.out.println("최대 합: " + maxSoFar);
    System.out.println("시작 인덱스: " + start + ", 끝 인덱스: " + end);
}

6. 복잡도 분석

요약

1. 배열을 순회합니다.
2. 현재 숫자를 누적 합에 더합니다.
3. 비교: (누적 합)보다 (현재 숫자 혼자)가 더 큰가? 그렇다면 누적 합을 버리고 현재 숫자부터 다시 시작(Reset) 합니다.
4. 현재 누적 합이 역대 최고 기록보다 높으면 기록을 갱신합니다.

이 문제는 "2차원 문제를 1차원 문제로 축소(Reduction)" 하는 것이 핵심입니다.

1. 핵심 아이디어: "열 압축하기 (Squashing)"

2차원 행렬이 있다고 상상해 보세요. 만약 우리가 특정 두 개의 열(예: 왼쪽(L) 경계와 오른쪽(R) 경계)을 선택한 뒤, 그 사이에 있는 모든 숫자를 행(Row)별로 더해서 눌러버린다면(Squash) 어떻게 될까요?

결과는 1차원 배열이 됩니다.

이렇게 1차원 배열을 만들고 나면, 그 안에서 "최고의 구간"을 찾는 것은 우리가 이미 아는 기본 카데인 알고리즘을 돌리면 끝나는 문제입니다.

2. 알고리즘 (단계별 설명)

행렬의 크기가 $R \times C$ (행 $\times$ 열)라고 가정합시다.

1. 왼쪽 열($L$) 고정: $L$을 $0$부터 $C-1$까지 반복합니다.
2. 임시 1차원 배열(temp) 초기화: 크기가 $R$이고 모두 0인 배열을 만듭니다.
3. 오른쪽 열($R$) 확장: $R$을 $L$부터 $C-1$까지 반복합니다.
4. 행 합계 누적 (압축): 오른쪽 열 포인터가 이동할 때마다, 그 열의 값을 temp 배열에 더합니다.
   • temp[row] += matrix[row][right]
   • 이제 temp[i]는 $L$열부터 $R$열까지 가로로 긴 띠의 $i$번째 행의 합을 의미합니다.
5. 1차원 카데인 수행: 만들어진 temp 배열에 대해 카데인 알고리즘을 수행합니다.
   • 이 결과값은 $L$열과 $R$열 사이로 한정했을 때 얻을 수 있는 최대 부분 직사각형의 합입니다.
6. 전체 최대값 갱신: 이 값이 지금까지의 최대값보다 크다면 갱신합니다.

3. 시각적 예시

다음과 같은 $4 \times 5$ 행렬이 있다고 합시다.

$$\begin{bmatrix} 1 & 2 & -1 & -4 & -20 \ -8 & -3 & 4 & 2 & 1 \ 3 & 8 & 10 & 1 & 3 \ -4 & -1 & 1 & 7 & -6 \end{bmatrix}$$

현재 반복 단계:

• 왼쪽 열 ($L$) = 1
• 오른쪽 열 ($R$) = 2

이 두 열 사이에 있는 값들을 행별로 더해 temp 배열로 압축합니다:

• 0행: $2 + (-1) = 1$
• 1행: $-3 + 4 = 1$
• 2행: $8 + 10 = 18$
• 3행: $-1 + 1 = 0$

생성된 temp 배열: [1, 1, 18, 0]

이제 [1, 1, 18, 0]에 대해 1차원 카데인 알고리즘을 돌립니다:

• 최대 부분 합은 $1+1+18+0 = 20$입니다.
• 이 숫자의 의미: 1열부터 2열 사이, 그리고 0행부터 3행 사이에 있는 직사각형의 합이 20이라는 뜻입니다.

4. 구현 코드 (Java)

이 로직을 효율적으로 구현한 Java 코드입니다.

import java.util.Arrays;

public class MaximumSumRectangle {
    
    public int maxSumRectangle(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int globalMax = Integer.MIN_VALUE;
        
        // Left와 Right 열 사이의 행들의 합을 저장할 임시 배열
        int[] temp = new int[rows];

        // 1. 왼쪽 열(Left) 고정
        for (int left = 0; left < cols; left++) {
            
            // 새로운 시작점을 잡을 때마다 temp 배열을 0으로 초기화
            Arrays.fill(temp, 0);
            
            // 2. 오른쪽 열(Right) 확장
            for (int right = left; right < cols; right++) {
                
                // 3. 현재 오른쪽 열의 값을 temp에 누적 (2차원을 1차원으로 압축)
                for (int i = 0; i < rows; i++) {
                    temp[i] += matrix[i][right];
                }
                
                // 4. 압축된 1차원 배열에 대해 카데인 알고리즘 수행
                int currentKadaneSum = kadane(temp);
                
                if (currentKadaneSum > globalMax) {
                    globalMax = currentKadaneSum;
                }
            }
        }
        
        return globalMax;
    }

    // 표준 1차원 카데인 알고리즘
    private int kadane(int[] nums) {
        int maxSoFar = nums[0];
        int currentMax = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
        }
        return maxSoFar;
    }
}

5. 복잡도 분석

행(Rows)을 $R$, 열(Cols)을 $C$라고 합시다.

• 단순 무식한 방법 (Brute Force):
  • 시작점(좌상단)과 끝점(우하단)을 모두 골라야 하므로 가능한 직사각형의 수는 $O(R^2 C^2)$입니다.
  • 매번 합을 구하는 데 $O(R \times C)$가 듭니다.
  • 총합: $O(R^3 C^3)$ (매우 비효율적입니다).
• 2D 카데인 알고리즘:
  • left 루프: $C$번 반복.
  • right 루프: $C$번 반복.
  • temp 누적: $R$번 반복.
  • 카데인 수행: $R$번 반복.
  • 총합: $C \times C \times (R + R) \approx$ $O(C^2 R)$.

최적화 팁:

만약 행이 열보다 훨씬 많다면($R \gg C$), 위 방식($O(C^2 R)$)이 유리합니다.

반대로 열이 행보다 훨씬 많다면($C \gg R$), 로직을 회전시켜 위/아래 행을 고정하고 열을 압축하는 것이 좋습니다. 이 경우 시간 복잡도는 $O(R^2 C)$가 됩니다.

일반적으로 복잡도는 $O(\min(R, C)^2 \times \max(R, C))$ 라고 표현할 수 있습니다.

MaxProduct 구하기

기본 카데인 알고리즘(합 구하기)과는 다르게, 곱하기에는 아주 중요한 수학적 반전이 숨어 있습니다.

음수 \times 음수 = 양수

이 규칙 때문에, 현재 시점에서 "아주 작은 음수(예: -100)" 는 나중에 "아주 큰 양수" 가 될 잠재력을 가지고 있습니다. 따라서 단순히 최댓값만 추적해서는 안 되며, 최댓값(Max)과 최솟값(Min)을 동시에 추적해야 합니다.

1. 핵심 로직: 이중 추적 (Dual Tracking)

모든 인덱스 i에서, 숫자 $nums[i]$를 포함한 최대 곱은 다음 세 가지 경우 중 하나입니다.

1. 숫자 그 자체 (이전 값들을 버리고 새로 시작).
2. 현재 수 $\times$ 이전까지의 최댓값 (양수 $\times$ 양수).
3. 현재 수 $\times$ 이전까지의 최솟값 (음수 $\times$ 음수 $\rightarrow$ 거대한 양수 반전).

따라서 우리는 매 단계마다 두 개의 변수를 갱신해야 합니다.

• currentMax: 여기서 끝나는 가장 큰 곱.
• currentMin: 여기서 끝나는 가장 작은(가장 큰 음수 절댓값을 가진) 곱.

2. 알고리즘 단계

1. currentMax, currentMin, globalMax를 배열의 첫 번째 원소로 초기화합니다.
2. 두 번째 원소부터 끝까지 순회합니다.
3. 각 숫자 n에 대하여:

• 임시 변수를 사용해 값을 계산합니다. (계산 중에 currentMax가 변해버리면 currentMin 계산이 꼬이기 때문입니다.)
• $NewMax = \max(n, \quad n \times currentMax, \quad n \times currentMin)$
• $NewMin = \min(n, \quad n \times currentMax, \quad n \times currentMin)$
• globalMax를 갱신합니다.

3. 트레이스 테이블 (시각화)

예제 배열: [2, 3, -2, 4, -1]을 추적해 봅시다.

초기화: curMax = 2, curMin = 2, 결과(Result) = 2

결과: 최대 곱 부분 배열은 48입니다 (해당 구간: [3, -2, 4, -1]).

4. 구현 코드 (Java)

Java 구현 코드입니다. tempMax 변수를 사용하여 currentMin을 계산할 때 업데이트 전의 maxSoFar 값을 사용하는 것에 주의하세요.

public class MaxProductSubarray {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;

        int maxSoFar = nums[0];
        int minSoFar = nums[0];
        int result = maxSoFar;

        for (int i = 1; i < nums.length; i++) {
            int curr = nums[i];
            
            // maxSoFar가 먼저 업데이트되면 minSoFar 계산이 틀려지므로 
            // 임시 변수나 계산 순서에 주의해야 합니다.
            int tempMax = Math.max(curr, Math.max(curr * maxSoFar, curr * minSoFar));
            int tempMin = Math.min(curr, Math.min(curr * maxSoFar, curr * minSoFar));

            maxSoFar = tempMax;
            minSoFar = tempMin;

            result = Math.max(maxSoFar, result);
        }

        return result;
    }
}

5. 다른 방법: "스왑(Swap)" 로직

Python이나 C++ 풀이에서 자주 보이는 똑똑한 트릭이 있습니다. 음수를 곱하면 가장 컸던 값은 가장 작아지고, 가장 작았던 값은 가장 커집니다. 따라서 nums[i] < 0일 때, maxSoFar와 minSoFar를 맞바꾸면(Swap) 계산이 훨씬 단순해집니다.

// 루프 내부 로직
int curr = nums[i];

// 음수를 만나면 Max와 Min을 교체
if (curr < 0) {
    int temp = maxSoFar;
    maxSoFar = minSoFar;
    minSoFar = temp;
}

// 이제 기본 카데인 로직처럼 수행
maxSoFar = Math.max(curr, curr * maxSoFar);
minSoFar = Math.min(curr, curr * minSoFar);

6. 0(Zero) 처리

만약 중간에 0이 있으면 어떻게 될까요?

• 예: [2, 0, 4]
• 0을 만나면 곱셈 결과가 모두 0이 되어버립니다. (maxSoFar, minSoFar 모두 0이 됨)
• 그다음 4를 만나면 max(4, 4 * 0)이 되어 4부터 자연스럽게 **새로 시작(Reset)**하게 됩니다.
• 별도의 예외 처리가 필요 없습니다.

요약

1. Max와 Min을 둘 다 추적하십시오.
2. Min이 필요한 이유는 **음수 \times Min = Max(최대값)**이 될 수 있기 때문입니다.
3. 매 단계마다 다음 셋 중 가장 큰 값을 선택합니다:
   • 새로 시작 (nums[i])
   • 현재 값 \times Max
   • 현재 값 \times Min
4. 시간 복잡도: O(N)
5. 공간 복잡도: O(1)

references